# -*- coding: utf-8 -*-
"""
Created on Thu Oct 18 17:37:54 2018

@author: duxiaoqin
Functions:
    (1)Puzzle8 class;
"""
import time

from myarray2d import Array2D
from priorityqueue import PriorityQueue
from stack import Stack
from random import *


class Puzzle8:
    HEIGHT = 3
    WIDTH = 3
    ITEMS = [' ', '1', '2', '3', '4', '5', '6', '7', '8']
    GOAL = Array2D(HEIGHT, WIDTH)
    for row in range(HEIGHT):
        for col in range(WIDTH):
            GOAL[row, col] = ITEMS[row * WIDTH + col]

    def __init__(self, clone=False):
        self.__puzzle8 = Array2D(Puzzle8.HEIGHT, Puzzle8.WIDTH)
        self.__cost_so_far = 0
        self.__inversions = 0
        self.num = ''

        if (clone == False):
            self._genRandomItems()
            self._calcInversions()
            while self.__inversions % 2 != 0:
                self._genRandomItems()
                self._calcInversions()
            self.__heuristics = self._calcHeuristics()
            self.num = self._num()

    def _genRandomItems(self):
        items = Puzzle8.ITEMS[:]
        for row in range(Puzzle8.HEIGHT):
            for col in range(Puzzle8.WIDTH):
                index = randint(0, len(items) - 1)
                item = items[index]
                self[row, col] = item
                if item == ' ':
                    self.__space = (row, col)
                items.remove(item)

    def _calcInversions(self):
        def merge_sort(items):
            if len(items) <= 1:
                return items
            pos = len(items) // 2
            half1 = items[:pos]
            half2 = items[pos:]
            left = merge_sort(half1)
            right = merge_sort(half2)
            return merge(left, right)

        def merge(left, right):
            list = []
            while len(left) > 0 and len(right) > 0:
                item1 = left[0]
                item2 = right[0]
                if item1 <= item2:
                    list.append(left.pop(0))
                else:
                    self.__inversions += len(left)
                    list.append(right.pop(0))
            list.extend(left)
            list.extend(right)
            return list

        self.__inversions = 0
        items = [int(self[row, col]) \
                 for row in range(Puzzle8.HEIGHT) \
                 for col in range(Puzzle8.WIDTH) \
                 if self[row, col] != ' ']
        merge_sort(items)

    def clone(self):
        new = Puzzle8(clone=True)
        for row in range(Puzzle8.HEIGHT):
            for col in range(Puzzle8.WIDTH):
                new[row, col] = self[row, col]
        new.__cost_so_far = self.__cost_so_far
        new.__heuristics = self.__heuristics
        new.__space = self.__space
        return new

    def isGoal(self):
        for row in range(Puzzle8.HEIGHT):
            for col in range(Puzzle8.WIDTH):
                if self[row, col] != Puzzle8.GOAL[row, col]:
                    return False
        return True

    def __lt__(self, other):  # for PriorityQueue
        return self.heuristics < other.heuristics

    def _calcHeuristics(self):
        heuristics = 0
        for row in range(Puzzle8.HEIGHT):
            for col in range(Puzzle8.WIDTH):
                item = self[row, col]
                if item != ' ':
                    index = Puzzle8.ITEMS.index(item)
                    row1 = index // Puzzle8.WIDTH
                    col1 = index % Puzzle8.WIDTH
                    heuristics += abs(row1 - row) + abs(col1 - col)
        return heuristics

    def __getitem__(self, ndxTuple):
        return self.__puzzle8.__getitem__(ndxTuple)

    def __setitem__(self, ndxTuple, value):
        self.__puzzle8.__setitem__(ndxTuple, value)

    def numRows(self):
        return self.__puzzle8.numRows()

    def numCols(self):
        return self.__puzzle8.numCols()

    def getAllMoves(self):
        row = self.__space[0]
        col = self.__space[1]
        moves = []
        offsets = [(0, -1), (-1, 0), (1, 0), (0, 1)]
        for x, y in offsets:
            x = col + x
            y = row + y
            if x < 0 or x > Puzzle8.WIDTH - 1 or \
                    y < 0 or y > Puzzle8.HEIGHT - 1:
                continue
            moves.append((y, x))
        return moves

    def move(self, row, col):
        self[self.__space[0], self.__space[1]] = self[row, col]
        self[row, col] = ' '
        self.__space = (row, col)
        self.__cost_so_far += 1
        self.__heuristics = self._calcHeuristics()
        self.num = self._num()

    def _num(self):
        s = ''
        for row in range(Puzzle8.HEIGHT):
            for col in range(Puzzle8.WIDTH):
                s += self[row, col]
        return s

    @property
    def cost(self):
        return self.__cost_so_far

    @property
    def heuristics(self):
        return self.__heuristics

    def ToString(self):
        items = [self[row, col] for row in range(Puzzle8.HEIGHT) \
                 for col in range(Puzzle8.WIDTH)]
        return ''.join(items)

    def print(self):
        for row in range(Puzzle8.HEIGHT):
            for col in range(Puzzle8.WIDTH):
                print(self[row, col], end=' ')
            print()


def Astar(puzzle8, came_fram):
    srcPuzzle8SerP = parityArrangement(puzzle8)
    goalPuzzle8SerP = parityArrangement(puzzle8.GOAL)
    if (srcPuzzle8SerP % 2) != (goalPuzzle8SerP % 2):  # 一个奇数一个偶数，不可达
        print("无解")
        # return None
    frontier = PriorityQueue()
    cost_so_for = {}
    frontier.enqueue(puzzle8, 0)
    cost_so_for[puzzle8] = puzzle8.cost
    came_fram[puzzle8] = None
    while not frontier.is_empty():
        puzzle8 = frontier.dequeue()
        if puzzle8.isGoal():
            return puzzle8
        else:
            # 临接元组
            for criticalTuple in puzzle8.getAllMoves():
                newPuzzle = puzzle8.clone()
                # 移动
                newPuzzle.move(criticalTuple[0], criticalTuple[1])
                # 获取权值
                new_cost = newPuzzle.cost
                if newPuzzle not in cost_so_for or new_cost < cost_so_for[newPuzzle]:
                    cost_so_for[newPuzzle] = new_cost
                    property = new_cost + newPuzzle.heuristics
                    frontier.enqueue(newPuzzle, property)
                    came_fram[newPuzzle] = puzzle8
    return None


def parityArrangement(puzzle8):
    lsi = []
    for row in range(puzzle8.numRows()):
        for col in range(puzzle8.numCols()):
            if puzzle8[row, col] != ' ':
                # lsi.append(0)
                # else:
                lsi.append(int(puzzle8[row, col]))
    print("当前排列：", lsi)

    src = 0
    print("当前逆序：", end="[")
    for index in range(0, len(lsi)):
        fist = 0
        for ids in range(0, index):
            if lsi[ids] < lsi[index] != '0' and lsi[ids] != '0':  # 0是false,'0'才是数字
                fist = fist + 1
        if index == len(lsi) - 1:
            print(fist, end="]\n")
        else:
            print(fist, end=",")
        src = fist + src
    print("当前逆序值：", src)
    return src


def main():
    seed()

    puzzle8 = Puzzle8()
    print("*****原*****")
    puzzle8.print()
    print("*****目标*****")
    Puzzle8.GOAL.print()

    came_fram = {}
    t1 = time.perf_counter()
    found = Astar(puzzle8, came_fram)
    t2 = time.perf_counter()
    print("搜索用时", t2 - t1)
    i = 0
    if found is not None:
        pathFinishing = Stack()
        pathFinishing.push(found)
        found = came_fram.get(found)
        while found is not None:
            pathFinishing.push(found)
            found = came_fram.get(found)
        while not pathFinishing.is_empty():
            i += 1
            print("******", i, " 次******")
            pathFinishing.pop().print()


if __name__ == '__main__':
    main()
